1. Field of the Invention
The invention relates to an adder having a carry foreknowledge (carry lookahead) circuit for the purpose of raising a speed of an arithmetic operation and, more particularly, to the improvement for realization of a high speed of an arithmetic operation of a carry foreknowledge circuit.
2. Related Background Art
An adder constructed by a logic circuit is fundamentally an adder of a binary number (1 or 0) of one digit and, in the case of adding an addition number Ai (binary number of one digit) and an adding number Bi (binary number of one digit), when a carry output from one-lower digit is assumed to be a carry input Cin, an addition result Si (binary number of one digit) is shown by the following equation.Si=Ai+Bi+Cin  (1)
In the equation (1) and equations which will be shown hereinbelow, “i” denotes a positive integer such as 0, 1, 2, 3, . . . , shows a current digit number to be arithmetically operated upon, and indicates to which digit of a plurality of digits each of the shown numbers corresponds. A sign “+” shows a logical sum (OR) such as an OR element or the like. Cin denotes the carry output and is also expressed by a binary number of one digit.
Since the addition result Si is expressed by a binary number of one digit and (Ai+Bi+Cin) denotes the OR of three binary numbers, when the addition result Si is outputted, a carry output Ci in the case where a carry occurs is also outputted. The carry output Ci is shown by the following equation.Ci=Ai·Bi+(Ai+Bi)·Cin  (2)
In the equation (2) and equations which will be shown hereinbelow, a sign “.” denotes a logical product (AND) such as an AND element or the like.
For example, in a ripple carry adder or the like in which all adders of one digit are serially connected, the adder waits until the carry output (Cin) of a lower digit is arithmetically determined and inputted, and thereafter, arithmetic operations of the addition result Si and the carry output Ci of the upper digit are executed.
A carry foreknowledge circuit is a circuit for checking the generation of the carry output of the lower digit and grasping the carry output corresponding to it. For example, when the OR “Ai+Bi” is defined as a propagation signal Pi and the AND “Ai+Bi” is defined as a generation signal Gi, the equations (1) and (2) are shown by the following equations.Si=Pi+Cin  (3)Ci=Gi+Pi·Cin  (4)
Since “in” of “Cin” indicates a digit which is lower by one digit than the current digit number “i” which is arithmetically operated upon, it can be also shown as “i−1”.
Specific examples of the carry output are expressed by the following equations with respect to the lowest digit up to the fourth digit. A general equation is shown at the end.C0=G0+P0·Cin C1=G1+P1·C0C2=G2+P2·C1C3=G3+P3·C2Cj=Gj+Pj·C(j−1)  (5)where, “j” is a positive integer such as 0, 1, 2, 3, . . . .
From the above examples of the carry outputs, by substituting each lower carry output into the upper carry output and developing each equation, the following equations are obtained. A general equation is shown at the end.
                                                        C0              =                              G0                +                                  P0                  ·                  Cin                                                                                                                                                              C1                    =                                          G1                      +                                              P1                        ·                                                  (                                                      G0                            +                                                          P0                              ·                              Cin                                                                                )                                                                                                                                                                                      =                                          G1                      +                                              P1                        ·                        G0                                            +                                              P1                        ·                        P0                        ·                        Cin                                                                                                                                                                                                                          C2                    =                                          G2                      +                                              P2                        ·                                                  (                                                      G1                            +                                                          P1                              ·                              C0                                                                                )                                                                                                                                                                                      =                                          G2                      +                                              P2                        ·                        G1                                            +                                              P2                        ·                        P1                        ·                        C0                                                                                                                                                              =                                          G2                      +                                              P2                        ·                        G1                                            +                                              P2                        ·                        P1                        ·                                                  (                                                      G0                            +                                                          P0                              ·                              Cin                                                                                )                                                                                                                                                                                      =                                          G2                      +                                              P2                        ·                        G1                                            +                                              P2                        ·                        P1                        ·                        G0                                            +                                              P2                        ·                        P1                        ·                        P0                        ·                        Cin                                                                                                                                                                                                                          C3                    =                                        ⁢                                          G3                      +                                              P3                        ·                                                  (                                                      G2                            +                                                          P2                              ·                              C1                                                                                )                                                                                                                                                                                      =                                        ⁢                                          G3                      +                                              P3                        ·                        G2                                            +                                              P3                        ·                        P2                        ·                        C1                                                                                                                                                              =                                        ⁢                                          G3                      +                                              P3                        ·                        G2                                            +                                              P3                        ·                        P2                        ·                                                  (                                                      G1                            +                                                          P1                              ·                                                              (                                                                  G0                                  +                                                                      P0                                    ·                                    Cin                                                                                                  )                                                                                                              )                                                                                                                                                                                      =                                        ⁢                                          G3                      +                                              P3                        ·                        G2                                            +                                              P3                        ·                        P2                        ·                        G1                                            +                                              P3                        ·                        P2                        ·                        P1                        ·                                                  (                                                      G0                            +                                                          P0                              ·                              Cin                                                                                )                                                                                                                                                                                      =                                        ⁢                                          G3                      +                                              P3                        ·                        G2                                            +                                              P3                        ·                        P2                        ·                        G1                                            +                                                                                                                                                            ⁢                                                                  P3                        ·                        P2                        ·                        P1                        ·                        G0                                            +                                              P3                        ·                        P2                        ·                        P1                        ·                        P0                        ·                        Cin                                                                                                                                                                                                                ⁢                                                                    ·                                                        ·                                                                                                                                                                                Cj                    =                                          Gj                      +                                              Pj                        ·                                                  G                          ⁡                                                      (                                                          j                              -                              1                                                        )                                                                                              +                                              Pj                        ·                                                  P                          ⁡                                                      (                                                          j                              -                              1                                                        )                                                                          ·                                                  G                          ⁡                                                      (                                                          j                              -                              2                                                        )                                                                                              +                                                                                                                                                                                                      ⁢                                                                  Pj                        ⁢                                                                                                  ⁢                        …                        ⁢                                                                                                  ⁢                                                  P3                          ·                          P2                          ·                          P1                          ·                          G0                                                                    +                                              Pj                        ⁢                                                                                                  ⁢                        …                        ⁢                                                                                                  ⁢                                                  P3                          ·                          P2                          ·                          P1                          ·                          P0                          ·                          Cin                                                                                                                                                                            (        6        )            
A circuit to realize the equations (6) is called a carry foreknowledge circuit of j [bit]. According to a carry foreknowledge adder having the carry foreknowledge circuit, by directly executing carry calculations of the upper digits from all inputs of the lower digits, they can be arithmetically calculated in parallel by adding circuits of the respective digits. Unlike a ripple carry adder or the like, since it is unnecessary to wait until the carry output of the one-lower digit (previous digit) is inputted even in the case where the digit number is large, an arithmetic operating speed can be raised.
However, the carry foreknowledge circuit has a problem such that the larger the number of digits is, the larger a circuit scale of the carry foreknowledge circuit becomes at a rate near the square of the digit number. Therefore, in the carry foreknowledge adder, for example, a plurality of carry foreknowledge circuits of about 4 bits (4 digits) are used, a numerical value larger than 4 bits is divided into groups (addition digit groups) every 4 bits (fixed length), and the addition is executed for every group in parallel.
The carry foreknowledge adder preliminarily arithmetically operates in the case where the carry input Cin from the lower group is equal to 0 and in the case where it is equal to 1 in every group and selects one of them on the basis of the carry input Cin from the group of the lower digits. That is, only the selection from two kinds of arithmetic operation results in the group of the upper digits is sequentially made by the carry output from the group of the lowest digits. Since the arithmetic operation is not started by the carry input Cin from the group of the lower digits, total arithmetic operating time is reduced.
FIG. 5 is a block diagram showing an example of a construction of an 8-bit adder using the carry foreknowledge adding circuits of 4 bits.
The left half of FIG. 5 shows the carry foreknowledge adding circuit of 4 bits on the lower side and the right half shows the carry foreknowledge adding circuit of 4 bits on the upper side.
An addition number A0 and an adding number B0 for a lower 4-bit block are inputted to a Pi/Gi generating circuit. A generation signal G0 and a propagation signal P0 of the lowest digit are generated and inputted to the carry foreknowledge circuit of 4 bits for the lower 4-bit block, and a carry output C0 is arithmetically determined. The propagation signal P0 is arithmetically operated upon together with the carry input Cin from the 4-bit adding circuit of the lower digit and an addition result S0 is arithmetically determined.
An addition number A1 and an adding number B1 for a lower 4-bit block are inputted to the Pi/Gi generating circuit. A generation signal G1 and a propagation signal P1 of the second digit from the lowest digit are generated and inputted to the carry foreknowledge circuit of 4 bits, and a carry output C1 is arithmetically determined. A propagation signal P1 is arithmetically operated upon together with the carry output C0 of the lowest digit and an addition result S1 is arithmetically determined.
Similarly, a generation signal G2 and a propagation signal P2 of the third digit from the lowest digit are generated from an addition number A2 and an adding number B2. A carry output C2 is arithmetically determined in the carry foreknowledge circuit. An addition result S2 is arithmetically determined from the propagation signal P2 and the carry output C1. A generation signal G3 and a propagation signal P3 of the highest digit of the lower 4-bit block are generated from an addition number A3 and an adding number B3. In the carry foreknowledge circuit, a carry output C3 is arithmetically determined and an addition result S3 is arithmetically determined from the propagation signal P3 and the carry output C2. The carry output C3 is transmitted to the carry foreknowledge adding circuit on the upper 4-bit side.
In the carry foreknowledge adding circuit on the upper 4-bit side, the carry output C3 is used as a carry input Cin and arithmetic operations similar to those in the carry foreknowledge adding circuit on the lower 4-bit side are executed upon the addition number Ai and the adding number Bi of each digit.
FIG. 6 is a block diagram showing a construction of the Pi/Gi generating circuit of each digit in the carry foreknowledge adding circuit of 4 bits.
As shown in FIG. 6, since the propagation signal Pi is the OR, the OR “Ai+Bi”=Pi can be outputted by inputting the addition number Ai and the adding number Bi to an OR circuit. Similarly, since the generation signal Gi is the AND, the AND “Ai·Bi”=Gi can be outputted by inputting the addition number Ai and the adding number Bi to an AND circuit.
FIG. 7 is a block diagram showing an example of the 4-bit carry foreknowledge circuit in FIG. 5 together with the Pi/Gi generating circuit.
A circuit at the first stage in FIG. 7 is a circuit in which in the Pi/Gi generating circuits shown in FIG. 6 as many as four digits are provided every digit as shown in FIG. 5. The generation signal Gi and the propagation signal Pi of each digit are generated by the circuit at the first stage.
Subsequently, in the first digit (in the case for lower 4 bits; the fifth digit in the case for upper 4 bits) in FIG. 7, the addition number A0 and the adding number B0 of the lowest digit are inputted and the generation signal G0 and the propagation signal P0 are generated by the circuit of the first stage. In an AND circuit AN62, the AND of the propagation signal P0 and the carry input Cin from the lower digit group is arithmetically determined and P0·Cin is outputted. In an OR circuit OR62, the OR of the generation signal G0 and P0·Cin is arithmetically determined and G0+P0·Cin is outputted.
As shown in the above equations (6), since G0+P0·Cin is equal to C0, C0=G0+P0·Cin in the above equations (6) is satisfied.
In the second digit (sixth digit in the case for upper 4 bits), the addition number A1 and the adding number B1 of the second digit from the lowest digit are inputted and the generation signal G1 and the propagation signal P1 are generated by the circuit of the first stage. In an AND circuit AN72, the AND of the propagation signal P0 and the carry input Cin is arithmetically determined and P0·Cin is outputted. In an AND circuit AN73, the AND of the propagation signal P1 and P0·Cin is arithmetically determined and P1·P0·Cin is outputted. In an AND circuit AN74, the AND of the propagation signal P1 and the generation signal G0 is arithmetically determined and P1·G0 is outputted. In an OR circuit OR72, P1·P0·Cin and P1·G0 are inputted and P1·G0+P1·P0·Cin is outputted. In an OR circuit OR73, P1·G0+P1·P0·Cin and the generation signal G1 are inputted and G1+P1·G0+P1·P0·Cin is outputted.
Since G1+P1·G0+P1·P0·Cin is equal to C1 as shown in the equations (6), C1=G1+P1·G0+P1·P0·Cin in the equations (6) mentioned above is satisfied.
Since an explanation is complicated with respect to the third and fourth digits, it is omitted. However, in a manner similar to the above, first, with respect to the third digit, G2+P2·G1+P2·P1·G0+P2·P1·P0·Cin is outputted from an OR circuit OR83. As described in the above equations, G2+P2·G1+P2·P1·G0+P2·P1·P0·Cin is equal to C2. Therefore, C2=G2+P2·G1+P2·P1·G0+P2·P1·P0·Cin in the equations (6) mentioned above is satisfied.
Subsequently, with respect to the fourth digit, G3+P3·G2+P3·P2·G1+P3·P2·P1·G0+P3·P2·P1·P0·Cin is outputted from an OR circuit OR95. As described in the above equations, G3+P3·G2+P3·P2·G1+P3·P2·P1·G0+P3·P2·P1·P0·Cin is equal to C3. Therefore, C3=G3+P3·G2+P3·P2·G1+P3·P2·P1·G0+P3·P2·P1·P0·Cin in the equations (6) mentioned above is satisfied.
As mentioned above, according to the conventional carry foreknowledge adder having the carry foreknowledge circuits, the arithmetic operations are executed in parallel in the adding circuits of the respective digits by directly executing the carry calculation of the upper digits by using all inputs of the lower digits, so that even if the number of digits is large, the arithmetic operating speed is raised.
However, as will be understood from FIG. 7, in the case of outputting the carry output C3 of the fourth digit, first, it is necessary that the carry input Cin from the lower digit group is inputted to an AND circuit AN92 and arithmetically operated by five circuits (5 elements) comprising the AND circuit AN92, an OR circuit OR92, an AND circuit AN98, an OR circuit OR94, and the OR circuit OR95. That is, in the conventional carry foreknowledge adder, the carry output C3 of the fourth digit is outputted only after the carry input Cin from the lower digit group was inputted and passed through the arithmetic operations of a critical path of five elements. The operation such that the carry input is arithmetically operated via the critical path of five elements results in that delay time corresponding to it is caused.
When the equations (6) are examined in detail, the carry input Cin from the lower digit group is necessary only in the last term in the equations (6). If it is shown in the case of the general equation in the equations (6), the last term is the term of the portion of “Pj . . . P3·P2·P1·P0·Cin”. If it is shown in the case of the carry output C3 of the fourth digit, the last term is the term of the portion of “P3·P2·P1·P0·Cin”.
As a carry foreknowledge adder, since there is a correlation between the digit number and the circuit scale as mentioned above, a plurality of circuits of about 4 bits (4 digits) are often used. Therefore, the case of the 4-bit adder will be considered hereinbelow. In this case, in the arithmetic operations to obtain the carry output C3 of the fourth digit, only the arithmetic operation of “P3·P2·P1·P0·Cin” needs the input of the carry input Cin from the lower digit group. If the circuit of the portion to execute the arithmetic operation of “P3·P2·P1·P0 Cin” can be arranged to the final stage of the carry foreknowledge adder, the arithmetic operations can be preliminarily executed with respect to the terms other than the last term in the equations (6). An amount of arithmetic operations which are executed after the input of the carry input Cin from the lower digit group can be reduced. Thus, the arithmetic operating speed can be raised.
However, hitherto, a circuit for further arithmetically determining the AND of the carry input Cin from the lower digit group and the AND arithmetic operation result of the propagation signals Pi of all digits such as “P3 P2 P1·P0” and the like at the final stage of an arbitrary digit of the carry foreknowledge circuit is not known.